<!doctype html>



  


<html class="theme-next mist use-motion">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>



<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />












  
  
  <link href="/vendors/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/vendors/font-awesome/css/font-awesome.min.css?v=4.4.0" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.0.1" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="Data Structure," />








  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.0.1" />






<meta name="description" content="说明：数据结构概论，常用算法。">
<meta name="keywords" content="Data Structure">
<meta property="og:type" content="article">
<meta property="og:title" content="Data Structure">
<meta property="og:url" content="http://bebetter.site/2017/03/01/Algorithm/Data Structure/index.html">
<meta property="og:site_name" content="gatewayzy">
<meta property="og:description" content="说明：数据结构概论，常用算法。">
<meta property="og:updated_time" content="2017-03-01T05:58:04.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Data Structure">
<meta name="twitter:description" content="说明：数据结构概论，常用算法。">



<script type="text/javascript" id="hexo.configuration">
  var NexT = window.NexT || {};
  var CONFIG = {
    scheme: 'Mist',
    sidebar: {"position":"right","display":"always"},
    fancybox: true,
    motion: true,
    duoshuo: {
      userId: 0,
      author: '博主'
    }
  };
</script>




  <link rel="canonical" href="http://bebetter.site/2017/03/01/Algorithm/Data Structure/"/>

  <title> Data Structure | gatewayzy </title>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  










  
  
    
  

  <div class="container one-collumn sidebar-position-right page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-meta ">
  

  <div class="custom-logo-site-title">
    <a href="/"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">gatewayzy</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
  <p class="site-subtitle">blog of gatewayzy</p>
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      

      
    </ul>
  

  
</nav>

 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  
  

  
  
  

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
            
            
              
                Data Structure
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">
            <span class="post-meta-item-icon">
              <i class="fa fa-calendar-o"></i>
            </span>
            <span class="post-meta-item-text">发表于</span>
            <time itemprop="dateCreated" datetime="2017-03-01T13:58:04+08:00" content="2017-03-01">
              2017-03-01
            </time>
          </span>

          
            <span class="post-category" >
              &nbsp; | &nbsp;
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
              
                <span itemprop="about" itemscope itemtype="https://schema.org/Thing">
                  <a href="/categories/Algorithm/" itemprop="url" rel="index">
                    <span itemprop="name">Algorithm</span>
                  </a>
                </span>

                
                

              
            </span>
          

          
            
          

          

          
          

          
        </div>
      </header>
    


    <div class="post-body" itemprop="articleBody">

      
      

      
        <p><strong>说明：</strong>数据结构概论，常用算法。<br><a id="more"></a></p>
<hr>
<ul>
<li>参考文章：<ul>
<li>《大话数据结构》</li>
<li>《算法导论》</li>
</ul>
</li>
</ul>
<h2 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h2><hr>
<ul>
<li>逻辑结构：集合结构、线性结构、树形结构、图形结构</li>
<li>物理结构：<ul>
<li>顺序存储结构：内存连续，直接计算前后地址（支持随机存取）。要提前指定空间大小并考虑溢出问题，快速高效，不适合元素频繁移动的情况</li>
<li>链接存储结构：内存不连续，使用指针等链接起来。不考虑大小，适合元素移动，但是需要额外空间实现遍历，查找不够快速</li>
</ul>
</li>
<li>每个逻辑结构都可以用不同的物理结构实现。<ul>
<li>内存申请与释放需要进行malloc、free操作。</li>
</ul>
</li>
</ul>
<h2 id="算法"><a href="#算法" class="headerlink" title="算法"></a>算法</h2><hr>
<ul>
<li>算法复杂度<ul>
<li>时间复杂度与空间复杂度，一般默认指时间复杂度</li>
<li>时间复杂度与空间复杂度一般需要进行折中考虑</li>
<li>复杂度的计算主要依靠数学能力。</li>
</ul>
</li>
<li><p>算法时间复杂度</p>
<ul>
<li>推导方法：求出语句执行次数关于问题规模的函数，选取增长率最快的并将系数取1。</li>
<li>常用O阶：O(1)&lt;O(log(n))&lt;O(n)&lt;O(nlog(n))&lt;O(n*n)&lt;…一般高于n方的就算太高了。</li>
<li>最坏情况与最好情况：分别可以求出一个最好O阶和最坏O阶。</li>
<li>根据所有情况的概率分布也可以求出一个平均运行时间。</li>
<li>一般时间复杂度是指最坏时间复杂度。</li>
</ul>
</li>
<li><p>算法空间复杂度</p>
<ul>
<li>推导方法：求出程序占用空间关于问题规模的函数，选取增长率最快的并将系数取1。</li>
<li>其他内容与算法时间复杂度类似。</li>
</ul>
</li>
</ul>
<h2 id="线性表"><a href="#线性表" class="headerlink" title="线性表"></a>线性表</h2><hr>
<ul>
<li>定义：0或多个数据元素的有限序列（每个数据元素可能含有多个数据项）</li>
</ul>
<h3 id="用顺序存储结构实现线性表"><a href="#用顺序存储结构实现线性表" class="headerlink" title="用顺序存储结构实现线性表"></a>用顺序存储结构实现线性表</h3><hr>
<ul>
<li>顺序存储结构存储，如数组array</li>
<li>优点：容易计算相对位置，查找迅速O(1)</li>
<li>缺点：改删元素需要内存连续性整理，需要考虑空间溢出与重新分配，太多的顺序结构可能造成内存碎片。</li>
</ul>
<h3 id="用链式存储结构实现线性表"><a href="#用链式存储结构实现线性表" class="headerlink" title="用链式存储结构实现线性表"></a>用链式存储结构实现线性表</h3><hr>
<ul>
<li>用链式存储结构存储，如列表List</li>
</ul>
<h4 id="单链表"><a href="#单链表" class="headerlink" title="单链表"></a>单链表</h4><ul>
<li>头指针与头结点的异同<ul>
<li>头指针指向链表第一个结点，如果有头结点就指向头结点。头指针不能为空，常用链表名标识整个链表</li>
<li>头结点是为了操作统一和方便而设立的，放在第一个元素之前，多数是存在的，便于统一在第一个数据结点插入数据的操作统一。</li>
</ul>
</li>
<li>链表操作<ul>
<li>增查改删等</li>
<li>查找要从头找，复杂度O(n)</li>
<li>插入时有头插法和尾插法，头插法就是新插入的结点放在第一个位置，尾插法就是放在尾部。</li>
<li>删除时就是从头一直往后删，释放内存。</li>
</ul>
</li>
</ul>
<h4 id="静态链表"><a href="#静态链表" class="headerlink" title="静态链表"></a>静态链表</h4><ul>
<li>静态链表：用数组实现的链表</li>
<li>方法：数组中每个对象有数据域和指针域（游标），指针域用于指向下一个链表结点。</li>
<li>优点：插入和删除只需要修改游标，不需要移动元素</li>
<li>缺点：失去原有数组结构的随机存取特征，需要考虑元素溢出时的内存申请问题。</li>
</ul>
<h4 id="循环链表"><a href="#循环链表" class="headerlink" title="循环链表"></a>循环链表</h4><ul>
<li>循环链表定义：将单链表的尾部结点的null指针改为指向头结点，就是一个头尾相接的单循环链表，简称循环链表。</li>
<li>如果需要方便查找尾结点，可以将头指针改成尾指针，每次从尾部节点开始。</li>
</ul>
<h4 id="双向链表"><a href="#双向链表" class="headerlink" title="双向链表"></a>双向链表</h4><ul>
<li>定义：在单链表的每个结点中添加一个指向前向结点的指针域就构成双线链表。</li>
</ul>
<h4 id="双向循环链表"><a href="#双向循环链表" class="headerlink" title="双向循环链表"></a>双向循环链表</h4><ul>
<li>将双线链表的头尾互联。</li>
</ul>
<h2 id="栈与队列"><a href="#栈与队列" class="headerlink" title="栈与队列"></a>栈与队列</h2><hr>
<h3 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h3><hr>
<ul>
<li>栈定义：只允许在表位进行插入和删除操作的线性表。</li>
<li>栈的特性：栈顶，栈底，出栈入栈，后进先出LIFO（last in first out）</li>
<li>具体实现示例如下。</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div></pre></td><td class="code"><pre><div class="line">Stack&lt;Integer&gt; stack = new Stack&lt;&gt;();  // java.util.Stack</div><div class="line">stack.push(1);</div><div class="line">stack.push(2);</div><div class="line"></div><div class="line">System.out.println(stack.peek()); // peek 获取栈顶元素，不会进行删除操作</div><div class="line">System.out.println(stack.pop());  // pop 获取栈顶元素，并从栈顶删除</div><div class="line">System.out.println(stack.size() + &quot;\t&quot; + stack.isEmpty()); //还有clear等和扩展实现的get、contains等</div></pre></td></tr></table></figure>
<h4 id="用线性存储结构实现栈"><a href="#用线性存储结构实现栈" class="headerlink" title="用线性存储结构实现栈"></a>用线性存储结构实现栈</h4><ul>
<li>用数组实现栈操作，a[0]存放栈底，后面的作为栈顶，以方便实现入栈出栈。</li>
<li>两个栈共享空间：将两个栈用同一个数组实现，数组两端分别做为两个栈底，栈向中间增长。适合于一个增那么另一个就减的情况。</li>
</ul>
<h4 id="用链式存储结构实现栈"><a href="#用链式存储结构实现栈" class="headerlink" title="用链式存储结构实现栈"></a>用链式存储结构实现栈</h4><ul>
<li>栈的链式存储结构简称为链栈。</li>
<li>可以用链表实现，只允许在链表尾部进行操作即可。</li>
</ul>
<h4 id="栈的应用–递归"><a href="#栈的应用–递归" class="headerlink" title="栈的应用–递归"></a>栈的应用–递归</h4><ul>
<li>栈经常用于递归的实现。</li>
<li>例如对于斐波那契，列出可以用简单的迭代和递归进行实现<ul>
<li>迭代：使用两个中间变量，从a0和a1循环迭代a[i-2]+a[i-1] = a[i] 直到目标。（迭代通过循环结构进行控制）</li>
<li>递归：调用自身，使用递归退出条件。（递归通过条件结构进行控制）</li>
</ul>
</li>
<li>迭代与递归的优缺点<ul>
<li>迭代不会占用额外的空间，不会反复调用函数本身，时间和空间比递归要好。但是设计要求也高一点。</li>
<li>递归会大量复制自身代码，占用大量的时间和内存，时间和空间都差，每一层迭代的局部变量、参数值和返回地址都会入栈，结束后再出栈接着执行该层递归的剩余代码。递归的好处在于设计实现起来简单。</li>
</ul>
</li>
</ul>
<h4 id="栈的应用–四则运算表达式求值"><a href="#栈的应用–四则运算表达式求值" class="headerlink" title="栈的应用–四则运算表达式求值"></a>栈的应用–四则运算表达式求值</h4><ul>
<li>中缀表达式就是平常写的加减乘除和括号的式子，后缀表达式就是不需要括号，将符号写在数字后面的式子（又叫后波兰表达式）。</li>
<li>用栈进行四则表达式的求值的过程为：<ul>
<li>将中缀表达式转化为后缀表达式（栈用于进出符号）。</li>
<li>将后缀表达式计算出结果（栈用于进出数字）。</li>
</ul>
</li>
<li>中缀表达式转后缀表达式<ul>
<li>遇到数字则直接输出。</li>
<li>遇到符号，如果优先级比栈顶符号高，则入栈；如果优先级比栈顶的低，则出栈并输出。<ul>
<li>若是右括号则进行出栈和输出，直至左括号出栈。（不输出左括号，且右括号不入栈）</li>
<li>若是左括号则入栈。</li>
</ul>
</li>
<li>从左向右处理原来表达式，输出结果连起来就是后缀表达式。如<code>9+(3-1)*3+10/2</code> 的后缀表达式为 <code>9 3 1 - 3 * + 10 2 / +</code> 。为了分开数字与数字，需要生成输出时输出空格。</li>
</ul>
</li>
<li>计算后缀表达式的值<ul>
<li>遇到数字则入栈</li>
<li>遇到符号则出栈两次，将三者计算结果入栈</li>
<li>直至从左向右计算完成可以得到最后结果。</li>
</ul>
</li>
</ul>
<h3 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h3><hr>
<ul>
<li>队列定义：只允许在一端插入、而在另一端删除的线性表。</li>
<li>队列特性：队尾插入、队首删除、先进先出（FIFO）</li>
<li>具体实现如下所示。</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div></pre></td><td class="code"><pre><div class="line">Queue&lt;Integer&gt; queue = new LinkedList&lt;&gt;();  // java.util.LinkedList实现了queue接口</div><div class="line">queue.add(1);</div><div class="line">queue.add(2);</div><div class="line"></div><div class="line">System.out.println(queue.peek());    // peek 获取队首，不会删除</div><div class="line">System.out.println(queue.poll());    // poll 获取并删除队首，空队会返回null</div><div class="line">System.out.println(queue.remove());  // remove 获取并删除队首，空队会抛出异常</div></pre></td></tr></table></figure>
<h4 id="用顺序存储结构实现队列"><a href="#用顺序存储结构实现队列" class="headerlink" title="用顺序存储结构实现队列"></a>用顺序存储结构实现队列</h4><ul>
<li>朴素的用数组实现队列：一头入队，另一头出队。<ul>
<li>缺点在于数组会出现假溢出，头部被删除的空间并没有利用上。</li>
</ul>
</li>
<li>循环队列：使用头尾相接的顺序存储结构实现的队列。<ul>
<li>用front和rear两个指针分别指向头结点和结尾元素的下一个节点</li>
<li>二者相等说明可能是空队列或者队列已满，队列长度计算方式为：（rear-front+QueueSize）%QueueSize</li>
<li>优点：适合用于队列最长长度确定的情况，</li>
<li>缺点：队列不满时有空间浪费，队列过长时需要重新申请内存。</li>
</ul>
</li>
</ul>
<h4 id="用链式存储结构实现队列"><a href="#用链式存储结构实现队列" class="headerlink" title="用链式存储结构实现队列"></a>用链式存储结构实现队列</h4><ul>
<li>用线性表的单链表实现队列，一端进另一端出，这种也简称为链队列。</li>
<li>单链表只允许头部进，尾部出，所以队列基本操作的时间复杂度也是O(1)。</li>
<li>链队列适合长度不好估计的情况，如果长度确定则应考虑用循环队列。</li>
</ul>
<h2 id="串"><a href="#串" class="headerlink" title="串"></a>串</h2><hr>
<ul>
<li>串、空串</li>
<li>串的存储结构：<ul>
<li>顺序存储结构：数组存储字符，最后添加一个’\0’作为结束表示（性能最好，一般用顺序存串）。</li>
<li>链式存储结构：链表存储：单链表的元素是多个字符。 </li>
</ul>
</li>
</ul>
<h3 id="串的模式匹配算法"><a href="#串的模式匹配算法" class="headerlink" title="串的模式匹配算法"></a>串的模式匹配算法</h3><hr>
<p>串中经常的之一就是模式匹配：从主串中查找子串的位置。</p>
<h4 id="朴素的模式匹配"><a href="#朴素的模式匹配" class="headerlink" title="朴素的模式匹配"></a>朴素的模式匹配</h4><ul>
<li>方法是使用主串每一个字符作为子串开头，与子串进行匹配。</li>
<li>需要强制实现二重循环匹配，缺点在于很多失败的匹配信息没有利用上。</li>
</ul>
<h4 id="KMP模式匹配算法"><a href="#KMP模式匹配算法" class="headerlink" title="KMP模式匹配算法"></a>KMP模式匹配算法</h4><ul>
<li>KMP是三个作者的姓名简写，KMP算法能够大大避免重复遍历的情况。当子串中重复部分比较多时，性能优势越明显。</li>
<li>朴素的KMP算法，核心思想就是主串的循环不进行回退，用相应的j进行控制。<ul>
<li>对子串进行计算next数组</li>
<li>根据子串的next的数组对主串进行匹配</li>
</ul>
</li>
<li><p>next数组的计算</p>
<ul>
<li>计算方法：<ul>
<li>next[j]=0，当j=1时</li>
<li>next[j]=Max{k | 1&lt;k&lt;j, 且‘P1…Pk-1’=‘Pj-k+1…Pj-1’} 当此集合不为空时</li>
<li>next[j]=1，在其他情况下</li>
</ul>
</li>
<li>示例：子串ababaaaba的next数组<ul>
<li>j=1，next[1]=0，对应a</li>
<li>j=2，前面部分是a，不能前后缀相同，next[2]=1;</li>
<li>j=3，前面部分是ab，不能前后缀相同，next[3]=1</li>
<li>j=4，前面部分是aba，最长相同是a与后面的a，next[4]=2(1个a+1)</li>
<li>j=5，前面部分是abab，最长相同是ab与后面的ab，next[5]=2+1=3</li>
<li>j=6，前面部分是ababa，最长相同是aba与后面的aba，next[6]=3+1=4</li>
<li>类推，得到 next[j] = 011234223</li>
</ul>
</li>
</ul>
</li>
<li><p>改进的KMP算法</p>
<ul>
<li>算法<ul>
<li>对子串计算next数组，同时，如果子串a位上的字符与他next值指向的b字符相等，则该a位的nextval的值设为b位的nextval值，如果不等则a的nextval就保留自己的next值。</li>
<li>根据子串的nextval数组对主串进行匹配</li>
</ul>
</li>
<li>示例：子串ababaaaba的nextval数组<ul>
<li>j=1，next[1]=0，nextval[1]=0</li>
<li>j=2，next[2]=1，子串1对应的是a，不等于当前2上的b，nextval[2]=next[2]=1</li>
<li>j=3，next[3]=1，子串1对应的是a，等于当前3上的a，nextval[3]=next[1]=0</li>
<li>j=4，next[4]=2，子串2对应的是b，等于当前4上的b，nextval[4]=next[2]=1</li>
<li>类推，得到nextval[j] = 010104210</li>
</ul>
</li>
</ul>
</li>
</ul>
<h2 id="树"><a href="#树" class="headerlink" title="树"></a>树</h2><hr>
<ul>
<li>树的递归定义、结点分类、森林：0个或多个不相交的树的集合</li>
</ul>
<h3 id="树的存储结构"><a href="#树的存储结构" class="headerlink" title="树的存储结构"></a>树的存储结构</h3><hr>
<ul>
<li>树的存储结构：用顺序存储比较麻烦，用链接存储比较方便</li>
<li>树的表示方式：<ul>
<li>双亲表示法</li>
<li>孩子表示法</li>
<li>孩子兄弟表示法</li>
</ul>
</li>
</ul>
<h3 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h3><hr>
<h4 id="基本知识"><a href="#基本知识" class="headerlink" title="基本知识"></a>基本知识</h4><ul>
<li>概念<ul>
<li>二叉树：所有结点至多2个孩子结点。</li>
<li>斜树：所有结点都只有一个方向的子结点，左斜树右斜树</li>
<li>满二叉树：所有分支结点都有2个子结点。</li>
<li>完全二叉树：所有结点的编号与相应深度的满二叉树中的结点按层编号的结果一致。</li>
</ul>
</li>
<li>二叉树的性质：结点树、树的高度等</li>
<li>二叉树的存储结构<ul>
<li>线性存储结构：二叉树由于结构特殊，用线性存储实现还是比较方便的，但是一般也只用于完全二叉树。</li>
<li>链式存储结构：用链表存储二叉树，又叫二叉链表。</li>
</ul>
</li>
</ul>
<h4 id="遍历二叉树"><a href="#遍历二叉树" class="headerlink" title="遍历二叉树"></a>遍历二叉树</h4><ul>
<li>遍历二叉树<ul>
<li>前序遍历：根节点–前序遍历左子树–后续遍历右子树</li>
<li>中序遍历：中序遍历左子树–根节点–中序遍历右子树</li>
<li>后序遍历：后续遍历左子树–后序遍历右子树–根节点</li>
<li>层次遍历：一层一层从左向右</li>
</ul>
</li>
<li>遍历的实现：方法1 递归 方法2 用栈实现<ul>
<li>根据中序遍历、前序遍历可以确定一棵二叉树</li>
<li>根据中序遍历、后续遍历可以确定一棵二叉树</li>
<li>但是由前序和后序遍历不能确定一个二叉树</li>
</ul>
</li>
<li>树、森林、二叉树的转换<ul>
<li>树转化为二叉树；加线、去线、层次调整</li>
<li>森林转化为二叉树：树转化为二叉树、树的根节点作为左边树根节点的右结点</li>
<li>二叉树转换为树：加线、去线、层次调整</li>
<li>二叉树转化为森林：断开根节点的顶层右结点，将各个二叉树转为树</li>
</ul>
</li>
<li>树的遍历：<ul>
<li>先根遍历</li>
<li>后根遍历</li>
</ul>
</li>
<li>森林的遍历：<ul>
<li>前序遍历</li>
<li>后序遍历</li>
</ul>
</li>
</ul>
<h4 id="赫夫曼树（最优二叉树）"><a href="#赫夫曼树（最优二叉树）" class="headerlink" title="赫夫曼树（最优二叉树）"></a>赫夫曼树（最优二叉树）</h4><ul>
<li>赫夫曼树<ul>
<li>路径长度：从根节点到目标结点间的分支树，如根节点到其子结点的路径长度为1</li>
<li>树的路径长度：从根节点到所有叶子结点的路径长度之和</li>
<li>带权路径：计算路径时计算上相应的权值</li>
<li><strong>赫夫曼树：带权路径最小的二叉树</strong></li>
<li>赫夫曼树的生成：选取最小的2个值构成二叉树，其权值之和与其余数值进行比较，再选取最小的2个值构成二叉树，直到完整一棵树</li>
<li>赫夫曼编码：将各个字母作为叶子结点，根据使用频率构造赫夫曼树，用0和1表示左右，从根节点到该结点的路径作为编码，可保证总的加密文本尽量短</li>
</ul>
</li>
</ul>
<h2 id="图"><a href="#图" class="headerlink" title="图"></a>图</h2><hr>
<h3 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h3><hr>
<ul>
<li>图的定义：由顶点的有穷非空集合和顶点之间边的集合组成，常记为G(V,E)，G表示图，V表示顶点的集合，E表示边</li>
<li>无向图：无向边(A,B)，有向图:有向边<a,b></a,b></li>
<li>简单图：不含有指向自身的边，同一条边不重复出现。无向（有向）完全图：顶点间全连接。</li>
<li>网：边上带权的图</li>
<li>子图，出度，入度</li>
<li>回路（环），简单路径，简单回路/简单环</li>
<li>连通图：任意两点间都连通的。有向图中均连通则叫强联通图</li>
<li>子图极大连通则为该图的连通分量，有向的则称为强连通分量</li>
<li>连通图的生成树：无向图中连通所有的n个结点且只含有n-1条边的连通子图</li>
<li>有向树：有向图中一顶点入度为0，其余顶点入度为1</li>
</ul>
<h3 id="图的存储结构"><a href="#图的存储结构" class="headerlink" title="图的存储结构"></a>图的存储结构</h3><hr>
<ul>
<li>图是逻辑上的，不管用顺序存储还是链式存储都比较复杂</li>
<li>图的存储表示方法：<ul>
<li><strong>邻接矩阵</strong>：  用一个数组存放顶点，用一个二维数组存放顶点之间是否连通或者路径距离（常用于最短路径、最小生成树）</li>
<li><strong>邻接表</strong>： 数组存放顶点，顶点后面使用链表存放该点相连的顶点（常用于拓扑排序等需要添加/删除节点的情况）</li>
<li>十字链表</li>
<li>邻接多重表</li>
<li>边集数组： 一个数组存放顶点，一个二维数组存放各个边的起始顶点、终止顶点、边的权值</li>
</ul>
</li>
</ul>
<h3 id="图的遍历"><a href="#图的遍历" class="headerlink" title="图的遍历"></a>图的遍历</h3><hr>
<ul>
<li>图的遍历：从一个顶点出发并只访问一次其余的所有顶点。</li>
<li>一般方法是设置一个数组标记顶点是否被访问过。</li>
</ul>
<h4 id="深度优先搜索-DFS"><a href="#深度优先搜索-DFS" class="headerlink" title="深度优先搜索 DFS"></a>深度优先搜索 DFS</h4><ul>
<li>深度优先搜索 depth first search（深度优先遍历），类似于图的先序遍历</li>
<li>思想：<ul>
<li>从图中一个节点出发，访问此顶点，然后对其未被访问过的邻接点进行DFS递归，直至所有点都被访问过</li>
<li>如果图是不连通的，则另选图中一个未被访问过的顶点进行DFS，直至所有点都被访问过</li>
</ul>
</li>
</ul>
<h4 id="广度优先搜索-BFS"><a href="#广度优先搜索-BFS" class="headerlink" title="广度优先搜索 BFS"></a>广度优先搜索 BFS</h4><ul>
<li>广度优先搜索 Breadth first search（广度优先遍历），类似于图的层序遍历</li>
<li>思想：<br>  * </li>
<li>深搜与广搜在时间复杂度上是一样的，在全图遍历上没有太多差别。但是由于顶点访问顺序不同，可能有不同的应用</li>
<li>常用场景：<ul>
<li>计算A与B之间最短路径、最短距离，一般用广搜</li>
</ul>
</li>
</ul>
<h3 id="最小生成树"><a href="#最小生成树" class="headerlink" title="最小生成树"></a>最小生成树</h3><ul>
<li>构造连通网的最小代价生成树称为最小生成树</li>
<li>用来解决同样问题的有Prim算法、Kruskal算法、Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。</li>
</ul>
<h4 id="Prim算法生成最小生成树"><a href="#Prim算法生成最小生成树" class="headerlink" title="Prim算法生成最小生成树"></a>Prim算法生成最小生成树</h4><ul>
<li>算法流程<ul>
<li>从一个顶点开始，放进点集合中</li>
<li>查找不在点集合中的所有点到点集合中各点权值最小的边，记录该边，并将对应点加入点集合</li>
<li>最后点集合会包含所有顶点，与记录的边构成最小生成树</li>
</ul>
</li>
<li>时间O阶为：邻接矩阵O（v*v） 邻接表O(elog(v)) ,e是边数，v是顶点数</li>
</ul>
<h4 id="Kruskal算法生成最小生成树"><a href="#Kruskal算法生成最小生成树" class="headerlink" title="Kruskal算法生成最小生成树"></a>Kruskal算法生成最小生成树</h4><ul>
<li>算法<ul>
<li>记Graph中有v个顶点，e个边</li>
<li>新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边</li>
<li>将原图Graph中所有e个边按权值从小到大排序</li>
<li>循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中<ul>
<li>if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中，添加这条边到图Graphnew中</li>
<li>否则放弃该边，选择下一条权值小的边。类推，直至所有顶点都在同一个连通分量上</li>
</ul>
</li>
</ul>
</li>
<li>Kruskal算法主要是针对边的，时间O阶是O(elog(e))其中e是边数，在边很少时效率很高，适用于稀疏图。对于稠密图，Prim算法更好些。</li>
</ul>
<h3 id="最短路径"><a href="#最短路径" class="headerlink" title="最短路径"></a>最短路径</h3><hr>
<ul>
<li>最短路径就是网图中从源点到终点经过的边上权值之和最少的路径。</li>
<li>Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法等</li>
</ul>
<h4 id="Dijkstra-算法"><a href="#Dijkstra-算法" class="headerlink" title="Dijkstra 算法"></a>Dijkstra 算法</h4><h4 id="Floyd-算法"><a href="#Floyd-算法" class="headerlink" title="Floyd 算法"></a>Floyd 算法</h4><h4 id="Bellman-Ford"><a href="#Bellman-Ford" class="headerlink" title="Bellman-Ford"></a>Bellman-Ford</h4><h4 id="SPFA"><a href="#SPFA" class="headerlink" title="SPFA"></a>SPFA</h4><h4 id="A-算法"><a href="#A-算法" class="headerlink" title="A*算法"></a>A*算法</h4><h3 id="拓扑排序"><a href="#拓扑排序" class="headerlink" title="拓扑排序"></a>拓扑排序</h3><hr>
<ul>
<li>AOV网络：顶点表示活动，弧表示活动之间的优先级的有向图。Activity On Vertex Network （vertex顶点） </li>
<li>拓扑序列：若从Vi顶点到Vj顶点有路径的话，在顶点排序中顶点Vi必须在Vj之前。</li>
<li>拓扑排序：对有向图构造拓扑序列。</li>
<li>算法思想：从AOV网络中选取入度为0的顶点输出，删除此顶点，删除此顶点出发的弧。重复上面的步骤，直到输出所有顶点或者没有入度为0的顶点。</li>
<li><p>由于排序要删除顶点，因此使用邻接表更加方便。 </p>
</li>
<li><p>算法实现：</p>
<ul>
<li>查找所有入度为0的顶点，入栈（避免重复查找每个每次删除之后都去查找入度为0的点）</li>
<li>出栈并进行输出、删除、删除弧操作，更新弧终点的入度，入度改变为0的话则入栈</li>
<li>重复上一步，直至栈为空</li>
</ul>
</li>
</ul>
<h3 id="关键路径"><a href="#关键路径" class="headerlink" title="关键路径"></a>关键路径</h3><hr>
<ul>
<li>AOE网络：带权有向图中，顶点表示事件，有向边表示活动，权值表示活动持续时间，这种网叫AOE网。Activity On Edge Network</li>
<li>路径长度：路径上各个活动持续的时间之和</li>
<li><p>关键路径：从源点到汇点（终点）的路径长度最大的路径。路径上的活动叫关键活动。</p>
</li>
<li><p>算法实现：</p>
</li>
</ul>
<h2 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h2><hr>
<h3 id="概念-1"><a href="#概念-1" class="headerlink" title="概念"></a>概念</h3><hr>
<ul>
<li>查找的关键字、主关键字、次关键字</li>
<li>静态查找表：查找时不改变原表，动态查找表：查找过程中插入或删除数据。</li>
<li>部分查找算法的复杂度</li>
</ul>
<table>
<thead>
<tr>
<th>分类</th>
<th>算法</th>
<th>最坏查找O阶</th>
<th>最坏插入O阶</th>
<th>最坏删除O阶</th>
<th>平均查找O阶</th>
<th>平均插入O阶</th>
<th>平均删除O阶</th>
<th>数据是否Ordered存放</th>
<th>思想</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>顺序表查找</strong></td>
<td>顺序表查找</td>
<td>n</td>
<td>n</td>
<td>n</td>
<td>n</td>
<td>n</td>
<td>n</td>
<td>否</td>
<td>对无序表一个一个查找</td>
</tr>
<tr>
<td><strong>有序表查找</strong></td>
<td>二分查找</td>
<td>log(n)</td>
<td>n</td>
<td>n</td>
<td>log(n)</td>
<td>n</td>
<td>n</td>
<td>是</td>
<td>对有序表进行划分查找，二分、插值、斐波那契等查找</td>
</tr>
<tr>
<td><strong>线性索引查找</strong></td>
<td>稠密索引、分块索引、倒排索引</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td>建立索引表，稠密索引、分块索引、倒排索引等</td>
</tr>
<tr>
<td><strong>二叉查找树</strong></td>
<td>BST二叉查找树</td>
<td>n</td>
<td>n</td>
<td>n</td>
<td>log(n)</td>
<td>log(n)</td>
<td>?</td>
<td>是</td>
<td>树的形状与插入顺序有关，没有平衡调节，可能偏</td>
</tr>
<tr>
<td>—-</td>
<td>AVL平衡二叉树</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>是</td>
<td>用BF平衡因子绝对值不大于1进行二叉树平衡，保证性能稳定</td>
</tr>
<tr>
<td>—-</td>
<td>RBT红黑树</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>是</td>
<td>用。。。进行二叉树平衡，保证性能稳定</td>
</tr>
<tr>
<td><strong>B树</strong></td>
<td>2-3树</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>log(n)</td>
<td>是</td>
<td>结点存放多个关键词，降低树高，减少查询次数，如2-3树，2-3-4树等</td>
</tr>
<tr>
<td><strong>B树变种</strong></td>
<td>B+树</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td>是</td>
<td>叶子存放关键词，非叶子结点只用于索引，并且每个叶子结点存放链接后一个叶子结点的指针</td>
</tr>
<tr>
<td>—-</td>
<td>B*树</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td>是</td>
<td>为B+树的非叶子结点也增加链表指针，将结点的最低利用率从1/2提升到2/3</td>
</tr>
<tr>
<td><strong>hash表查找</strong></td>
<td>hash表查找</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td>否</td>
</tr>
</tbody>
</table>
<h3 id="顺序表查找"><a href="#顺序表查找" class="headerlink" title="顺序表查找"></a>顺序表查找</h3><hr>
<p>顺序查找又叫线性查找，查找空间是线性的、无序的。</p>
<h4 id="朴素的顺序表查找方法"><a href="#朴素的顺序表查找方法" class="headerlink" title="朴素的顺序表查找方法"></a>朴素的顺序表查找方法</h4><ul>
<li>从数组头部开始向尾部查找，如果等于目标则输出并结束，查找不到则结束。</li>
</ul>
<h4 id="顺序表查找优化"><a href="#顺序表查找优化" class="headerlink" title="顺序表查找优化"></a>顺序表查找优化</h4><ul>
<li>如果a[0]等于key则返回</li>
<li><p>否则设置a[0]=key；i=n；while(a[i]!=key) {i–;} return i;</p>
</li>
<li><p>思想就是用key截断查找方向，好处在于不用每次都比较i是否超出n长度，可以有小幅度优化。当然也可以a[n-1]=key，从小向大查找。</p>
</li>
</ul>
<h3 id="有序表查找"><a href="#有序表查找" class="headerlink" title="有序表查找"></a>有序表查找</h3><hr>
<p>线性表有序时，进行查找可以利用顺序信息进行有效的优化。</p>
<h4 id="二分查找（折半查找）"><a href="#二分查找（折半查找）" class="headerlink" title="二分查找（折半查找）"></a>二分查找（折半查找）</h4><ul>
<li>关键思想：中间数比较，等于则输出；不等于则确定对左边或右边进行二分查找</li>
<li>时间O阶O(log(n))</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div></pre></td><td class="code"><pre><div class="line">/** </div><div class="line"> * 二分查找又称折半查找，它是一种效率较高的查找方法。【要求】：1.必须用顺序存储结构 2.必须按关键字有序排列。</div><div class="line"> */  </div><div class="line">public class BinarySearch &#123;   </div><div class="line">    public static void main(String[] args) &#123;  </div><div class="line">        int[] src = new int[] &#123;1, 3, 5, 7, 8, 9&#125;;   </div><div class="line">        System.out.println(binarySearch(src, 3));  </div><div class="line">        System.out.println(binarySearch(src,3,0,src.length-1));  </div><div class="line">    &#125;  </div><div class="line">  </div><div class="line">    /** </div><div class="line">     * 二分查找算法(循环实现)</div><div class="line">     */   </div><div class="line">   public static int binarySearch(int[] srcArray, int des)&#123;</div><div class="line">        int low = 0;   </div><div class="line">        int high = srcArray.length-1;   </div><div class="line">        while(low &lt;= high) &#123;   </div><div class="line">            int middle = (low + high)/2;   </div><div class="line">            if(des == srcArray[middle]) &#123;   </div><div class="line">                return middle;   </div><div class="line">            &#125;else if(des &lt;srcArray[middle]) &#123;   </div><div class="line">                high = middle - 1;   </div><div class="line">            &#125;else &#123;   </div><div class="line">                low = middle + 1;   </div><div class="line">            &#125;  </div><div class="line">        &#125;  </div><div class="line">        return -1;  </div><div class="line">   &#125;  </div><div class="line">        </div><div class="line">      /**   </div><div class="line">     *二分查找特定整数在整型数组中的位置(递归实现)</div><div class="line">     */  </div><div class="line">    public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex)&#123;    </div><div class="line">       int midIndex = (beginIndex+endIndex)/2;    </div><div class="line">       if(data &lt;dataset[beginIndex]||data&gt;dataset[endIndex]||beginIndex&gt;endIndex)&#123;  </div><div class="line">           return -1;    </div><div class="line">       &#125;  </div><div class="line">       if(data &lt;dataset[midIndex])&#123;    </div><div class="line">           return binarySearch(dataset,data,beginIndex,midIndex-1);    </div><div class="line">       &#125;else if(data&gt;dataset[midIndex])&#123;    </div><div class="line">           return binarySearch(dataset,data,midIndex+1,endIndex);    </div><div class="line">       &#125;else &#123;    </div><div class="line">           return midIndex;    </div><div class="line">       &#125;    </div><div class="line">   &#125;   </div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h4 id="插值查找"><a href="#插值查找" class="headerlink" title="插值查找"></a>插值查找</h4><ul>
<li>在二分查找中，对下一级的半部分进行查找时选用的是头和尾的0.5，如果将0.5改为（key-a[low]）/（a[high]-a[low]），就叫插值查找。</li>
<li>插值查找时间O阶O(log(n))</li>
<li>对于数据多、数据分布均匀的情况，插值查找效率比二分查找高。对于数据不多、分布不均匀的情况，二分查找比插值查找要好。</li>
</ul>
<h4 id="斐波那契查找"><a href="#斐波那契查找" class="headerlink" title="斐波那契查找"></a>斐波那契查找</h4><ul>
<li>使用斐波那契序列取代二分查找中的的二分定位方法</li>
</ul>
<h3 id="线性索引查找"><a href="#线性索引查找" class="headerlink" title="线性索引查找"></a>线性索引查找</h3><hr>
<p>索引查找长用于数据库、文件、搜索引擎等领域。</p>
<h4 id="稠密索引"><a href="#稠密索引" class="headerlink" title="稠密索引"></a>稠密索引</h4><ul>
<li>稠密索引：为每个数据建立索引，对索引进行二分、插值等查找。</li>
<li>数据量很多的时候不现实</li>
</ul>
<h4 id="分块索引"><a href="#分块索引" class="headerlink" title="分块索引"></a>分块索引</h4><ul>
<li>分块索引：将数据分块有序，块内无序，块间有序。</li>
<li>对每个块建立索引，查找的时候先查找块，然后内部进行顺序查找。</li>
</ul>
<h4 id="倒排索引"><a href="#倒排索引" class="headerlink" title="倒排索引"></a>倒排索引</h4><ul>
<li>倒排索引：用次关键字对主关键字记录建立索引的方式。</li>
<li>如对于good friend、good boy、a girl建立索引时用a对应3，good对应1,2，friend对应1，boy对应2，这样查找的时候就直接使用属性值的值查找记录，非常高效，即用属性值确定记录的位置。</li>
<li>倒排索引的优点是查找记录非常快，缺点是记录号不定长，且单词表在很长或者增删时都需要进行处理。常用于所有引擎的候选框等。</li>
<li>一般可以通过限定主键记录长度，记录编码压缩为110、+3等方式表示110、114等优化索引大小。</li>
</ul>
<h3 id="二叉排序树与平衡二叉树"><a href="#二叉排序树与平衡二叉树" class="headerlink" title="二叉排序树与平衡二叉树"></a>二叉排序树与平衡二叉树</h3><hr>
<p><strong>二叉查找树的缺点在于每个节点只存放一个元素值，每个节点最多有2个分支</strong>，导致大数据的时候，树会很高很大，查找需要多次循环。</p>
<h4 id="二叉排序树（二叉查找树）BST"><a href="#二叉排序树（二叉查找树）BST" class="headerlink" title="二叉排序树（二叉查找树）BST"></a>二叉排序树（二叉查找树）BST</h4><ul>
<li>二叉排序树，Binary Search Tree，BST，也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree）</li>
<li>二叉排序树：左子树的结点为空或者均小于根节点的值，右子树的结点为空或者均大于根节点，对左右子树进行递归要求。</li>
<li>二叉排序树的中序遍历就是所有结点从小到大。</li>
<li>查找方法：从根节点比较，相等则退出，否则对左右子树进行递归查找（与根的大小比较决定左还是右）。最外层有个循环控制是否查找不到。（将查找到的叶子结点返回以方便进行插入操作）</li>
<li>插入方法：查找判断，此时返回指针对应应该插入的叶子结点，已存在则不插入，不存在则比较是在左还是右新增结点。</li>
<li>删除方法：如果是其右子树为空则接上其左子树为左子树，如果其左子树为空则接上其右子树为其右子树，如果左右子树都不是空，则循环选取左子树中的右子树到结点即为左子树最大值，将最大值赋值给要删除的结点，将这个最大值结点释放，重接最大值的上下（判定删除的左子节点是不是最大的）。</li>
<li>二叉排序树在构造过程中，虽然是动态表，但是不会移动各个根节点，所以树的形状和插入顺序有很大关系，可能是斜树等情况，不够平衡。</li>
</ul>
<h4 id="平衡二叉树-AVL"><a href="#平衡二叉树-AVL" class="headerlink" title="平衡二叉树 AVL"></a>平衡二叉树 AVL</h4><ul>
<li>AVL树，平衡二叉树，AVL出自是论文作者名。</li>
<li>由于二叉排序树的形状数据插入的先后影响可能导致偏差，因此需要构造平衡稳定的二叉树将性能稳定下来。</li>
<li>平衡二叉树 Self-Balancing Binary Search Tree或者叫 Height-Balanced Binary Search Tree，属于二叉排序树</li>
<li>平衡因子BF：Balance Factor，指的是左子树深度-右子树深度。平衡二叉树要求BF的绝对值不超过1。</li>
<li>最小不平衡子树：插入一个结点后，距离插入节点最近且BF绝对值大于1的结点为根构成的子树，称为最小不平衡树。主要用于表示插入该节点后AVL可以进行重新构建平衡。</li>
<li>插入方法：每个结点都存储自己的BF，插入的时候，判断插入该叶子结点后是否出现最小Unbalance子树，如果出现BF为2说明左边多，需要右旋调整，如果出现BF为-2说明右边多，需要左旋调整。注意，如果最小Unbanlance子树的BF与其子树的BF符号相反，则需要先对该最小Unbanlance子树的子树进行一步旋转，再对该最小Unbanlance子树进行旋转平衡。</li>
</ul>
<h4 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h4><ul>
<li>Red-Black BST，参考文章<a href="http://algs4.cs.princeton.edu/33balanced/" target="_blank" rel="external">Balanced Search Trees</a>、<a href="http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html" target="_blank" rel="external">浅谈算法和数据结构:九平衡查找树之红黑树</a></li>
<li>红黑树的应用十分广泛，在多种编程语言中被用作符号表的实现，如：Java的TreeMap,TreeSet，C++ STL的map,multimap,multiset等。</li>
<li>B树在使用的时候非常麻烦，但是B树比BST多了平衡操作，将2-3树的平衡思想与二叉树结合起来就可以使用BST统一的分支处理，能够构建相对稳定的平衡树。</li>
<li>基于2-3树构建RBT的思想可以理解为：黑色链接用来链接普通的2-nodes节点。使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。也就是说将1个3结点的两个元素进行拆分，左边的值拉出来的结点设置为红色属性（存储的时候是每个节点都有颜色属性值，根节点为黑色）</li>
<li>红黑树具有且必须保持下列性质，否则需要进行平衡调节：<ul>
<li>每个结点是红色的或者是黑色的，根节点是黑色的。每个叶子结点是黑色的</li>
<li>如果一个节点是红色的，那么他的两个子结点都是黑色的</li>
<li>对每个节点，从他到其所有后代结点的简单路径上，均包含相同数量的黑色结点。</li>
</ul>
</li>
<li>红黑树的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。而又是一种平衡树。</li>
<li>插入算法：递归向下查找应该添加结点的分支结点，新插入的结点颜色为红色，对于下面三种情况<strong>依次</strong>进行判断（flipColor是必须在后面的）：<ul>
<li>如果一个节点的左子节点位黑色，右子节点为红色，则进行左旋操作（向左旋）</li>
<li>如果一个节点的左子节点为红色，而且该红色结点的左子节点也为红色，则进行右旋操作</li>
<li>如果一个节点的左右子节点均为红色，则执行FlipColor操作，提升中间结点（将两个子结点红色设置为黑色，自己设置为红）。</li>
</ul>
</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div></pre></td><td class="code"><pre><div class="line">public override void Put(TKey key, TValue value)</div><div class="line">&#123;</div><div class="line">    root = Put(root, key, value);</div><div class="line">    root.Color = BLACK;</div><div class="line">&#125;</div><div class="line"></div><div class="line">private Node Put(Node h, TKey key, TValue value)</div><div class="line">&#123;</div><div class="line">    if (h == null) return new Node(key, value, 1, RED);</div><div class="line">    int cmp = key.CompareTo(h.Key);</div><div class="line">    if (cmp &lt; 0) h.Left = Put(h.Left, key, value);</div><div class="line">    else if (cmp &gt; 0) h.Right = Put(h.Right, key, value);</div><div class="line">    else h.Value = value;</div><div class="line"></div><div class="line">    //平衡化操作</div><div class="line">    if (IsRed(h.Right) &amp;&amp; !IsRed(h.Left)) h = RotateLeft(h);</div><div class="line">    if (IsRed(h.Right) &amp;&amp; IsRed(h.Left.Left)) h = RotateRight(h);</div><div class="line">    if (IsRed(h.Left) &amp;&amp; IsRed(h.Right)) h = FlipColor(h);</div><div class="line"></div><div class="line">    h.Number = Size(h.Left) + Size(h.Right) + 1;</div><div class="line">    return h;</div><div class="line">&#125;</div><div class="line"></div><div class="line">private int Size(Node node)</div><div class="line">&#123;</div><div class="line">    if (node == null) return 0;</div><div class="line">    return node.Number;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<ul>
<li>AVL树与RBT的比较：<ul>
<li>AVL是严格的平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；</li>
<li>红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低开销；在最坏的情况下，红黑树的高度不超过2lgN（以2为底）</li>
<li>所以简单说，如果搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应选择红黑树。即，有时仅为了排序（建立-遍历-删除），不查找或查找次数很少，R-B树合算一些。</li>
<li>红黑树与AVL树的调整平衡的实现机制不同，AVL靠平衡因子和旋转，红黑树靠节点颜色以及一些约定再加上旋转。因此，存在去掉颜色的红黑树后它不是AVL树，比如左子树都是黑的，右子树都是红黑相间的，这样整个树高度2n的时候，根节点的左右层数差可以到n。</li>
</ul>
</li>
</ul>
<h3 id="多路查找树（B树）"><a href="#多路查找树（B树）" class="headerlink" title="多路查找树（B树）"></a>多路查找树（B树）</h3><hr>
<ul>
<li>多路查找树Multi-way Search Tree，允许每个结点存储M/2到M个关键字（结点利用率），非叶子结点存储指向关键字范围的子结点，以降低树的高度。</li>
<li><strong>所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中。</strong></li>
</ul>
<h4 id="B树（B-树）"><a href="#B树（B-树）" class="headerlink" title="B树（B-树）"></a>B树（B-树）</h4><ul>
<li>B树，B-树，B-Tree（Balanced树,不是指Binary！）。结点孩子树数目最大的数目为B树的阶。B树是一种平衡的多路查找树。2-3树，2-3-4树都是特殊的B树。常用于减少定位记录的用时，常用于文件系统和数据库。</li>
<li>一个m阶的B树要求如下：<ul>
<li>如果结点不是叶子结点，该结点至少有2个子树</li>
<li>每一个非根的分支结点都有k个孩子，本身包含k-1个元素值，其中k属于[(m+1)/2, m]，（子树分支在50% - 100% 阶）</li>
<li>所有叶子结点处于同一高度</li>
<li>所有结点上的k-1个元素将数据分为k段，分别指向子树，以进行查找操作。</li>
</ul>
</li>
<li>B树主要用于内外存交换，每次读取一个节点到内存，进行比较确定子树，读取子结点再进行比较等等。有些像多层索引，只不过索引匹配相等，树支持大小比较。</li>
</ul>
<h4 id="2-3树"><a href="#2-3树" class="headerlink" title="2-3树"></a>2-3树</h4><ul>
<li><a href="http://www.cnblogs.com/yangecnu/p/Introduce-2-3-Search-Tree.html" target="_blank" rel="external">浅谈算法和数据结构: 八 平衡查找树之2-3树</a></li>
<li>2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key</li>
<li>2-3查找树实现起来比较复杂。插入和删除操作也需要保证平衡性和结点利用率的范围限制问题，进行相应的左旋右旋、拆分等操作。</li>
<li>在2-3查找树基础上改进的红黑树不仅具有较高的效率，并且实现起来较2-3查找树简单。</li>
<li>2-3树只能包含2结点或者3结点，可以与2-3-4树比较。2结点就是自己有1个元素且其分支有0个或者2个。3结点就是自己有2个元素且其分支有0个或3个。</li>
</ul>
<h4 id="2-3-4树"><a href="#2-3-4树" class="headerlink" title="2-3-4树"></a>2-3-4树</h4><ul>
<li>4结点就是自己有3个元素且其分支有0个或4个，0表示是叶子结点，4表示是被3个数分割为4段区间。</li>
</ul>
<h3 id="B树变种"><a href="#B树变种" class="headerlink" title="B树变种"></a>B树变种</h3><hr>
<h4 id="B-树"><a href="#B-树" class="headerlink" title="B+树"></a>B+树</h4><ul>
<li><a href="http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html" target="_blank" rel="external">浅谈算法和数据结构: 十 平衡查找树之B树</a></li>
<li><strong>B+树不是严格意义上的树形数据结构。</strong></li>
<li>在B-树基础上，为叶子结点增加链表指针，<strong>所有关键字都在叶子结点中出现，</strong>非叶子结点只作为叶子结点的索引。可以通过叶子结点间的链表关系直接遍历全部记录。</li>
<li>B+树特别适用于范围查找，找到起始节点之后直接向后遍历取值。常用于文件系统、数据库等。</li>
<li>B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针</li>
</ul>
<h4 id="B-树-1"><a href="#B-树-1" class="headerlink" title="B*树"></a>B*树</h4><ul>
<li>在B+树基础上，为非叶子结点也增加链表指针，B*树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）</li>
<li>B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针</li>
</ul>
<h3 id="hash表查找"><a href="#hash表查找" class="headerlink" title="hash表查找"></a>hash表查找</h3><hr>
<p>hash（散列）适合处理关键字不相关的情况，直接将关键字去掉关联，查找的时候一步到位，时间O阶O(1)。需要注意的是hash函数的选择和hash冲突的处理方法。</p>
<h4 id="hash函数的选择"><a href="#hash函数的选择" class="headerlink" title="hash函数的选择"></a>hash函数的选择</h4><ul>
<li>hash函数选择需要：计算简单、分布均匀</li>
<li>常用方法：<ul>
<li>直接定址法：</li>
<li>平方取中法：</li>
<li>数字分析法：</li>
<li>平方取中法：</li>
<li>折叠法：</li>
<li>除留余数法：</li>
<li>随机数法：</li>
</ul>
</li>
</ul>
<h4 id="hash冲突处理"><a href="#hash冲突处理" class="headerlink" title="hash冲突处理"></a>hash冲突处理</h4><ul>
<li>常用方法：<ul>
<li>开放定址法：</li>
<li>再散列函数法：</li>
<li>链地址法：</li>
<li>公共溢出法：</li>
</ul>
</li>
</ul>
<h4 id="hash查找"><a href="#hash查找" class="headerlink" title="hash查找"></a>hash查找</h4><ul>
<li>时间O阶：<ul>
<li>最好时是O(1)，也就是没有冲突时。</li>
<li>但是平均O阶需要需要考虑hash函数的分布、冲突处理方法、hash表的装填因子（记录个数/hash表的长度）</li>
</ul>
</li>
</ul>
<h2 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h2><hr>
<ul>
<li><p>排序算法的分类：</p>
<ul>
<li>内排序、外排序（是否只使用内存）</li>
<li>稳定排序、不稳定排序（主键相同的记录是否会保持排序前的顺序）</li>
<li>比较排序与非比较排序</li>
</ul>
</li>
<li><p>算法比较</p>
<ul>
<li>参考文章：<a href="http://www.cnblogs.com/eniac12/p/5329396.html" target="_blank" rel="external">常用排序算法总结(一)</a></li>
</ul>
</li>
</ul>
<table>
<thead>
<tr>
<th style="text-align:center">分类</th>
<th style="text-align:center">算法</th>
<th style="text-align:center">最坏时间O阶</th>
<th style="text-align:center">最好时间O阶</th>
<th style="text-align:center">平均时间O阶</th>
<th style="text-align:center">辅助空间O</th>
<th style="text-align:center">是否稳定</th>
<th style="text-align:center">思想</th>
<th style="text-align:center">适合场景</th>
<th style="text-align:center">比较</th>
<th style="text-align:center">改进</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">简单算法</td>
<td style="text-align:center"><strong>冒泡排序bubbleSort</strong></td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$n$</td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$1$</td>
<td style="text-align:center">稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center">不太用</td>
<td style="text-align:center">经常最低效</td>
<td style="text-align:center">已有序flag、鸡尾酒排序（定向冒泡排序：排序方向从低到高与从高到低切换）</td>
</tr>
<tr>
<td style="text-align:center">—</td>
<td style="text-align:center"><strong>简单选择排序simple selection</strong></td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$1$</td>
<td style="text-align:center">稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center">可用于topN问题</td>
<td style="text-align:center">略优于bubble</td>
<td style="text-align:center"></td>
</tr>
<tr>
<td style="text-align:center">—</td>
<td style="text-align:center"><strong>直接插入排序straight    insertion</strong></td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$n$</td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$1$</td>
<td style="text-align:center">稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center">适用于基本有序或数量少</td>
<td style="text-align:center">略优于s selection</td>
<td style="text-align:center">若非基本有序,插入时要比较多次,可用二分查找插入</td>
</tr>
<tr>
<td style="text-align:center">改进算法</td>
<td style="text-align:center"><strong>希尔排序shell</strong></td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$n^{1.3}$</td>
<td style="text-align:center">$nlg(n)\sim n^2$</td>
<td style="text-align:center">$1$</td>
<td style="text-align:center">不稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center">第一个突破$n^2$限制的排序</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
<tr>
<td style="text-align:center">—</td>
<td style="text-align:center"><strong>堆排序heap</strong></td>
<td style="text-align:center">$nlg(n)$</td>
<td style="text-align:center">$nlg(n)$</td>
<td style="text-align:center">$nlg(n)$</td>
<td style="text-align:center">$1$</td>
<td style="text-align:center">不稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center">适用于topN问题</td>
<td style="text-align:center"></td>
</tr>
<tr>
<td style="text-align:center">—</td>
<td style="text-align:center"><strong>归并排序merging</strong></td>
<td style="text-align:center">$nlg(n)$</td>
<td style="text-align:center">$nlg(n)$</td>
<td style="text-align:center">$nlg(n)$</td>
<td style="text-align:center">$n$</td>
<td style="text-align:center">稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center">高效稳定</td>
<td style="text-align:center">递归与非递归</td>
</tr>
<tr>
<td style="text-align:center">—</td>
<td style="text-align:center"><strong>快速排序quick</strong></td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$nlg(n)$</td>
<td style="text-align:center">$nlg(n)$</td>
<td style="text-align:center">$lg(n)\sim n$</td>
<td style="text-align:center">不稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center">快速</td>
<td style="text-align:center">枢纽选取、交换策略</td>
</tr>
<tr>
<td style="text-align:center">以上都是比较排序，下面是非比较排序</td>
<td style="text-align:center"><strong>计数排序Counting</strong></td>
<td style="text-align:center">$n+k$</td>
<td style="text-align:center">$n+k$</td>
<td style="text-align:center">$n+k$ 最大最小之间所有</td>
<td style="text-align:center">$n$</td>
<td style="text-align:center">稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center">分布空间有限，如年龄排序</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
<tr>
<td style="text-align:center">—</td>
<td style="text-align:center"><strong>基数排序radix</strong></td>
<td style="text-align:center">$k* n$</td>
<td style="text-align:center">$k* n$</td>
<td style="text-align:center">$k* n$ k位数</td>
<td style="text-align:center">$n$</td>
<td style="text-align:center">稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
<tr>
<td style="text-align:center">—</td>
<td style="text-align:center"><strong>桶排序</strong></td>
<td style="text-align:center">$n^2$</td>
<td style="text-align:center">$n$</td>
<td style="text-align:center"></td>
<td style="text-align:center">$r+n$ r是桶个数</td>
<td style="text-align:center">稳定</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<ul>
<li>一个算法是否稳定常常与实现有关，比如简单选择排序，如果将最小(大)值进行交换可能导致不稳定，如{5,5,2}，但是如果新开辟数组添加{2,5,5}就可以是稳定的。</li>
<li>比较排序的分类：<ul>
<li>插入排序：直接插入排序 —— 希尔排序</li>
<li>交换排序：冒泡排序 —— 快速排序</li>
<li>选择排序：简单选择排序 —— 堆排序</li>
<li>归并排序：归并排序</li>
</ul>
</li>
<li><p>排序应用：</p>
<ul>
<li>算法没有最好，只是适合的场景不同，需要考虑数据的初始排序状态、时间限制、空间限制、稳定性限制、算法特性等</li>
<li>虽然改进算法比简单算法要复杂，但是一些情况下还是简单算法比较高效。如基本有序时用直插更高效。 </li>
</ul>
</li>
<li><p>堆排序</p>
<ul>
<li>堆排序一般用最大堆（所有父节点的值&gt;=子结点的值），最小堆一般用于构造优先队列。</li>
<li></li>
</ul>
</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div></pre></td><td class="code"><pre><div class="line">/**</div><div class="line"> * 堆排序</div><div class="line"> * 建立n次的最大堆，每次输出堆顶，对未输出的数字递归建堆输出。复杂度：建堆是log(n)，乘以n次就是n*log(n)</div><div class="line"> */</div><div class="line">public class HeapSort &#123;</div><div class="line">    public static void main(String[] args) &#123;</div><div class="line">        int[] a = &#123;7, 6, 0, 3, 2, 1, 4&#125;;</div><div class="line">        System.out.println(&quot;开始排序&quot;);</div><div class="line">        int arrayLength = a.length; // 循环建堆</div><div class="line">        for (int i = 0; i &lt; arrayLength - 1; i++) &#123; // 建堆</div><div class="line">            buildMaxHeap(a, arrayLength - 1 - i); // 交换堆顶和最后一个元素</div><div class="line">            swap(a, 0, arrayLength - 1 - i);</div><div class="line">        &#125;</div><div class="line">        System.out.println(Arrays.toString(a));</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    private static void swap(int[] data, int i, int j) &#123;</div><div class="line">        int tmp = data[i];</div><div class="line">        data[i] = data[j];</div><div class="line">        data[j] = tmp;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    // 对data数组从0到lastIndex建大顶堆</div><div class="line">    private static void buildMaxHeap(int[] data, int lastIndex) &#123;</div><div class="line">        // 从lastIndex处节点（最后一个节点）的父节点开始</div><div class="line">        for (int i = (lastIndex - 1) / 2; i &gt;= 0; i--) &#123;</div><div class="line">            // k保存正在判断的节点</div><div class="line">            int k = i;</div><div class="line">            // 如果当前k节点的子节点存在</div><div class="line">            while (k * 2 + 1 &lt;= lastIndex) &#123;</div><div class="line">                // k节点的左子节点的索引</div><div class="line">                int biggerIndex = 2 * k + 1;</div><div class="line">                // 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在</div><div class="line">                if (biggerIndex &lt; lastIndex) &#123;</div><div class="line">                    // 如果右子节点的值较大</div><div class="line">                    if (data[biggerIndex] &lt; data[biggerIndex + 1]) &#123;</div><div class="line">                        // biggerIndex总是记录较大子节点的索引</div><div class="line">                        biggerIndex++;</div><div class="line">                    &#125;</div><div class="line">                &#125;</div><div class="line">                // 如果k节点的值小于其较大的子节点的值</div><div class="line">                if (data[k] &lt; data[biggerIndex]) &#123;</div><div class="line">                    // 交换他们</div><div class="line">                    swap(data, k, biggerIndex);</div><div class="line">                    // 将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值</div><div class="line">                    k = biggerIndex;</div><div class="line">                &#125; else &#123;</div><div class="line">                    break;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<ul>
<li>快速排序<ul>
<li>优化方法：<ul>
<li>base优化：每次的base随机选取（随机化快速排序，适用于已有序的排序）、首尾和随机选取的均值作为base。</li>
<li>前后逼近策略修改：采用两个指针都从头向后逼近（可避免一些不必要的交换）。</li>
<li>小数组优化：改用直插排序。</li>
</ul>
</li>
</ul>
</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div></pre></td><td class="code"><pre><div class="line">import java.util.Arrays;</div><div class="line"></div><div class="line">/**</div><div class="line"> * 快速排序：两个指针从前面向后面逼近</div><div class="line"> */</div><div class="line">public class QuickSortFromLeft &#123;</div><div class="line">    public static void main(String[] args) &#123;</div><div class="line">        int[] data = new int[]&#123;1, 2, 6, 5, 4, 3, 7&#125;;</div><div class="line">        quickSort(data, 0, data.length - 1);</div><div class="line">        System.out.println(Arrays.toString(data));</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    static void quickSort(int[] data, int start, int end) &#123;</div><div class="line">        System.out.println(start + &quot; &quot; + end);</div><div class="line">        if (start == end) return;</div><div class="line">        int index = partition(data, start, end);</div><div class="line">        if (index &gt; start) &#123;</div><div class="line">            quickSort(data, start, index - 1);</div><div class="line">        &#125;</div><div class="line">        if (index &lt; end) &#123;</div><div class="line">            quickSort(data, index + 1, end);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">	</div><div class="line">	// partition就是将base值两侧排序好，并返回base所在index</div><div class="line">    static int partition(int[] data, int start, int end) &#123;</div><div class="line">        // 选取基准，可以头部、中间或者随机选取</div><div class="line">        int index = (start + end) / 2; // index = random(start,end)</div><div class="line">        swap(data, index, end); // 基准放在最后方便编程</div><div class="line"></div><div class="line">        int small = start - 1;</div><div class="line">        for (index = start; index &lt; end; ++index) &#123;</div><div class="line">            if (data[index] &lt; data[end]) &#123;</div><div class="line">                ++small;</div><div class="line">                if (small != index) &#123;</div><div class="line">                    swap(data, index, small);</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        ++small;</div><div class="line">        swap(data, small, end);</div><div class="line">        return small;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    static void swap(int[] data, int i, int j) &#123;</div><div class="line">        int tmp = data[i];</div><div class="line">        data[i] = data[j];</div><div class="line">        data[j] = tmp;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div></pre></td><td class="code"><pre><div class="line">/**</div><div class="line"> * 快速排序</div><div class="line"> * 每趟排序选一个基准（如第一个值），两端用指针向中间逼近，前面大于base，后面小于base的二者进行交换，直到中间位置。</div><div class="line"> * 递归前面到中间位置、中间位置到后面</div><div class="line"> *</div><div class="line"> */</div><div class="line">public class QuickSort &#123;</div><div class="line">    public static void main(String[] a) &#123;</div><div class="line">        int[] b = new int[]&#123;7, 6, 0, 3, 2, 1, 4&#125;;</div><div class="line">        quickSort(b, 0, b.length - 1);</div><div class="line">        System.out.println(Arrays.toString(b));</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    public static void quickSort(int[] numbers, int start, int end) &#123;</div><div class="line">        if (start &lt; end) &#123;</div><div class="line">            int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）</div><div class="line">            int temp; // 记录临时中间值</div><div class="line">            int i = start, j = end;</div><div class="line">            do &#123;</div><div class="line">                while ((numbers[i] &lt; base) &amp;&amp; (i &lt; end))</div><div class="line">                    i++;</div><div class="line">                while ((numbers[j] &gt; base) &amp;&amp; (j &gt; start))</div><div class="line">                    j--;</div><div class="line">                if (i &lt;= j) &#123;</div><div class="line">                    temp = numbers[i];</div><div class="line">                    numbers[i] = numbers[j];</div><div class="line">                    numbers[j] = temp;</div><div class="line">                    i++;</div><div class="line">                    j--;</div><div class="line">                &#125;</div><div class="line">            &#125; while (i &lt;= j);</div><div class="line">            if (start &lt; j)</div><div class="line">                quickSort(numbers, start, j);</div><div class="line">            if (end &gt; i)</div><div class="line">                quickSort(numbers, i, end);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>

      
    </div>

    <div>
      
        

      
    </div>

    <div>
      
        

      
    </div>

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/Data-Structure/" rel="tag">#Data Structure</a>
          
        </div>
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/01/14/AIMachineLearning/Statistical Learning Method/" rel="next" title="Statistical Learning Method">
                <i class="fa fa-chevron-left"></i> Statistical Learning Method
              </a>
            
          </div>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2017/03/01/Algorithm/Data Mining/" rel="prev" title="Data Mining">
                Data Mining <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  <div class="comments" id="comments">
    


  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel ">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/statics/images/avatar.png"
               alt="gatewayzy" />
          <p class="site-author-name" itemprop="name">gatewayzy</p>
          <p class="site-description motion-element" itemprop="description">blog website with hexo and github pages</p>
        </div>
        <nav class="site-state motion-element">
          <div class="site-state-item site-state-posts">
            <a href="/archives">
              <span class="site-state-item-count">70</span>
              <span class="site-state-item-name">日志</span>
            </a>
          </div>

          
            <div class="site-state-item site-state-categories">
              <a href="/categories">
                <span class="site-state-item-count">10</span>
                <span class="site-state-item-name">分类</span>
              </a>
            </div>
          

          
            <div class="site-state-item site-state-tags">
              <a href="/tags">
                <span class="site-state-item-count">38</span>
                <span class="site-state-item-name">标签</span>
              </a>
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
        </div>

        
        

        
        
          <div class="links-of-blogroll motion-element links-of-blogroll-inline">
            <div class="links-of-blogroll-title">
              <i class="fa  fa-fw fa-globe"></i>
              友情链接
            </div>
            <ul class="links-of-blogroll-list">
              
                <li class="links-of-blogroll-item">
                  <a href="https://github.com/gatewayzy" title="Github-gatewayzy" target="_blank">Github-gatewayzy</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://google.com/" title="Goolge" target="_blank">Goolge</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://wiki.jikexueyuan.com/" title="Wiki-jike" target="_blank">Wiki-jike</a>
                </li>
              
            </ul>
          </div>
        

      </section>

      
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">
            
              
            
            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#数据结构"><span class="nav-number">1.</span> <span class="nav-text">数据结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#算法"><span class="nav-number">2.</span> <span class="nav-text">算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#线性表"><span class="nav-number">3.</span> <span class="nav-text">线性表</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#用顺序存储结构实现线性表"><span class="nav-number">3.1.</span> <span class="nav-text">用顺序存储结构实现线性表</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#用链式存储结构实现线性表"><span class="nav-number">3.2.</span> <span class="nav-text">用链式存储结构实现线性表</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#单链表"><span class="nav-number">3.2.1.</span> <span class="nav-text">单链表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#静态链表"><span class="nav-number">3.2.2.</span> <span class="nav-text">静态链表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#循环链表"><span class="nav-number">3.2.3.</span> <span class="nav-text">循环链表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#双向链表"><span class="nav-number">3.2.4.</span> <span class="nav-text">双向链表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#双向循环链表"><span class="nav-number">3.2.5.</span> <span class="nav-text">双向循环链表</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#栈与队列"><span class="nav-number">4.</span> <span class="nav-text">栈与队列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#栈"><span class="nav-number">4.1.</span> <span class="nav-text">栈</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#用线性存储结构实现栈"><span class="nav-number">4.1.1.</span> <span class="nav-text">用线性存储结构实现栈</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#用链式存储结构实现栈"><span class="nav-number">4.1.2.</span> <span class="nav-text">用链式存储结构实现栈</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#栈的应用–递归"><span class="nav-number">4.1.3.</span> <span class="nav-text">栈的应用–递归</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#栈的应用–四则运算表达式求值"><span class="nav-number">4.1.4.</span> <span class="nav-text">栈的应用–四则运算表达式求值</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#队列"><span class="nav-number">4.2.</span> <span class="nav-text">队列</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#用顺序存储结构实现队列"><span class="nav-number">4.2.1.</span> <span class="nav-text">用顺序存储结构实现队列</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#用链式存储结构实现队列"><span class="nav-number">4.2.2.</span> <span class="nav-text">用链式存储结构实现队列</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#串"><span class="nav-number">5.</span> <span class="nav-text">串</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#串的模式匹配算法"><span class="nav-number">5.1.</span> <span class="nav-text">串的模式匹配算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#朴素的模式匹配"><span class="nav-number">5.1.1.</span> <span class="nav-text">朴素的模式匹配</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#KMP模式匹配算法"><span class="nav-number">5.1.2.</span> <span class="nav-text">KMP模式匹配算法</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#树"><span class="nav-number">6.</span> <span class="nav-text">树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#树的存储结构"><span class="nav-number">6.1.</span> <span class="nav-text">树的存储结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二叉树"><span class="nav-number">6.2.</span> <span class="nav-text">二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#基本知识"><span class="nav-number">6.2.1.</span> <span class="nav-text">基本知识</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#遍历二叉树"><span class="nav-number">6.2.2.</span> <span class="nav-text">遍历二叉树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#赫夫曼树（最优二叉树）"><span class="nav-number">6.2.3.</span> <span class="nav-text">赫夫曼树（最优二叉树）</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#图"><span class="nav-number">7.</span> <span class="nav-text">图</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#概念"><span class="nav-number">7.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#图的存储结构"><span class="nav-number">7.2.</span> <span class="nav-text">图的存储结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#图的遍历"><span class="nav-number">7.3.</span> <span class="nav-text">图的遍历</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#深度优先搜索-DFS"><span class="nav-number">7.3.1.</span> <span class="nav-text">深度优先搜索 DFS</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#广度优先搜索-BFS"><span class="nav-number">7.3.2.</span> <span class="nav-text">广度优先搜索 BFS</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最小生成树"><span class="nav-number">7.4.</span> <span class="nav-text">最小生成树</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#Prim算法生成最小生成树"><span class="nav-number">7.4.1.</span> <span class="nav-text">Prim算法生成最小生成树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Kruskal算法生成最小生成树"><span class="nav-number">7.4.2.</span> <span class="nav-text">Kruskal算法生成最小生成树</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最短路径"><span class="nav-number">7.5.</span> <span class="nav-text">最短路径</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#Dijkstra-算法"><span class="nav-number">7.5.1.</span> <span class="nav-text">Dijkstra 算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Floyd-算法"><span class="nav-number">7.5.2.</span> <span class="nav-text">Floyd 算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Bellman-Ford"><span class="nav-number">7.5.3.</span> <span class="nav-text">Bellman-Ford</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#SPFA"><span class="nav-number">7.5.4.</span> <span class="nav-text">SPFA</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#A-算法"><span class="nav-number">7.5.5.</span> <span class="nav-text">A*算法</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#拓扑排序"><span class="nav-number">7.6.</span> <span class="nav-text">拓扑排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#关键路径"><span class="nav-number">7.7.</span> <span class="nav-text">关键路径</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#查找"><span class="nav-number">8.</span> <span class="nav-text">查找</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#概念-1"><span class="nav-number">8.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#顺序表查找"><span class="nav-number">8.2.</span> <span class="nav-text">顺序表查找</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#朴素的顺序表查找方法"><span class="nav-number">8.2.1.</span> <span class="nav-text">朴素的顺序表查找方法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#顺序表查找优化"><span class="nav-number">8.2.2.</span> <span class="nav-text">顺序表查找优化</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#有序表查找"><span class="nav-number">8.3.</span> <span class="nav-text">有序表查找</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#二分查找（折半查找）"><span class="nav-number">8.3.1.</span> <span class="nav-text">二分查找（折半查找）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#插值查找"><span class="nav-number">8.3.2.</span> <span class="nav-text">插值查找</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#斐波那契查找"><span class="nav-number">8.3.3.</span> <span class="nav-text">斐波那契查找</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#线性索引查找"><span class="nav-number">8.4.</span> <span class="nav-text">线性索引查找</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#稠密索引"><span class="nav-number">8.4.1.</span> <span class="nav-text">稠密索引</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#分块索引"><span class="nav-number">8.4.2.</span> <span class="nav-text">分块索引</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#倒排索引"><span class="nav-number">8.4.3.</span> <span class="nav-text">倒排索引</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二叉排序树与平衡二叉树"><span class="nav-number">8.5.</span> <span class="nav-text">二叉排序树与平衡二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#二叉排序树（二叉查找树）BST"><span class="nav-number">8.5.1.</span> <span class="nav-text">二叉排序树（二叉查找树）BST</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#平衡二叉树-AVL"><span class="nav-number">8.5.2.</span> <span class="nav-text">平衡二叉树 AVL</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#红黑树"><span class="nav-number">8.5.3.</span> <span class="nav-text">红黑树</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#多路查找树（B树）"><span class="nav-number">8.6.</span> <span class="nav-text">多路查找树（B树）</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#B树（B-树）"><span class="nav-number">8.6.1.</span> <span class="nav-text">B树（B-树）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-3树"><span class="nav-number">8.6.2.</span> <span class="nav-text">2-3树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-3-4树"><span class="nav-number">8.6.3.</span> <span class="nav-text">2-3-4树</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#B树变种"><span class="nav-number">8.7.</span> <span class="nav-text">B树变种</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#B-树"><span class="nav-number">8.7.1.</span> <span class="nav-text">B+树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#B-树-1"><span class="nav-number">8.7.2.</span> <span class="nav-text">B*树</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#hash表查找"><span class="nav-number">8.8.</span> <span class="nav-text">hash表查找</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#hash函数的选择"><span class="nav-number">8.8.1.</span> <span class="nav-text">hash函数的选择</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#hash冲突处理"><span class="nav-number">8.8.2.</span> <span class="nav-text">hash冲突处理</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#hash查找"><span class="nav-number">8.8.3.</span> <span class="nav-text">hash查找</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#排序"><span class="nav-number">9.</span> <span class="nav-text">排序</span></a></li></ol></div>
            
          </div>
        </section>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy; 
  <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">gatewayzy</span>
</div>

<div class="powered-by">
  由 <a class="theme-link" href="https://hexo.io">Hexo</a> 强力驱动
</div>

<div class="theme-info">
  主题 -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Mist
  </a>
</div>

        

        
      </div>
    </footer>

    <div class="back-to-top">
      <i class="fa fa-arrow-up"></i>
    </div>
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  



  
  <script type="text/javascript" src="/vendors/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/vendors/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/vendors/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/vendors/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/vendors/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/vendors/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.0.1"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.0.1"></script>



  
  

  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.0.1"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.0.1"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.0.1"></script>



  



  




  
  

  
  <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
    });
  </script>

  <script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for (i=0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += ' has-jax';
      }
    });
  </script>
  <script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>



  

  
<script type="text/javascript" async src="//push.zhanzhang.baidu.com/push.js">
</script>


</body>
</html>
